package codetop.microsoft.T91;

import java.util.HashMap;
import java.util.Map;

/**
 * @Author: 18362
 * @Create: 2022-08-17 12:47:21 星期三
 */
class Solution {
    private int res;
    private Map<Integer, Integer> map = new HashMap<>();
    public int numDecodings(String s) {
        dfs(s, 0);
        return res;
    }

    private void dfs(String s, int cur) {
        if (cur == s.length()) {
            res++;
            return;
        }
        if (map.containsKey(cur)) {
            res += map.get(cur);
            return;
        }
        int oldRes = res;
        int curVal = s.charAt(cur) - '0';
        if (curVal != 0)
            dfs(s, cur+1);
        else
            return;
        if (cur < s.length()-1) {
            int val = curVal * 10 + s.charAt(cur+1) - '0';
            if (val <= 26)
                dfs(s, cur+2);
        }
        map.put(cur, res - oldRes);
    }
}